import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-10
 * Time: 9:05
 */

public class Solution {
//     滑动窗口 + 哈希桶
//     滑动窗口, 确定当前哈希桶中所有下标是满足条件的
//     哈希桶确定值是否满足条件
//     出现元素属于同一个哈希桶, 或者相邻两个桶满足条件的就返回结果
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 用哈希桶进行分类, 根据题意, 每个桶中只可能有一个元素, 有两个及以上就直接满足条件了, 直接就return 了
        Map<Long, Long> map = new HashMap<>();
        // 每个桶中元素个数为 t + 1
        long size = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
            long id = getId(nums[i], size);
            if (map.containsKey(id)){
                // 如果已经同一个桶中已经有元素了, 那么说明直接就是满足条件的
                return true;
            }
            // 滑动窗口限制了当前哈希桶中的元素的下标都是满足要求的
            // 所以我们只需要判断值是否满足要求
//             值满足要求, 要么在同一个桶中, 一定满足要求
//             要么在相邻桶中, 可能满足要求
            if (map.containsKey(id - 1) && Math.abs(map.get(id - 1) - nums[i]) <= t){
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(map.get(id + 1) - nums[i]) <= t){
                return true;
            }
            // 说明并没有符合条件的, 放到桶中
            map.put(id, (long)nums[i]);
            // 注意滑动窗口的大小为 k + 1 , 并不是 k, 所以因该放到循环的后面, 不能放到循环的开始
            if (i >= k){
                // 滑动窗口, 往右移动时删除第一个桶
                map.remove(getId(nums[i-k], size));
            }
        }
        return false;
    }

    /**
     * 对元素进行分桶, 每 t + 1 个相邻的元素同一个桶
     * @param value
     * @param size
     * @return
     */
    private long getId(int value, long size) {
        // 大于 0 的一种分法, 小于零的另一种
        // 都是为了满足 每 t + 1 个相邻的元素一个桶
        if (value >= 0){
            return value / size;
        }
        return (value + 1) / size - 1;
    }
}
